package org.example.myleet.p655;

import org.example.myleet.Utils.TreeNode;

import java.util.*;

public class Solution {

    public List<List<String>> printTree(TreeNode root) {
        int height = findHeightOfTree(root);
        List<List<String>> matrix = new ArrayList<>(height + 1);
        int n = (int) Math.pow(2, height + 1) - 1;
        for (int i = 0; i < height + 1; ++i) {
            List<String> row = new ArrayList<>(n);
            for (int j = 0; j < n; ++j) {
                row.add("");
            }
            matrix.add(row);
        }
        dfsFillMatrix(matrix, root, height, 0, n / 2);
        return matrix;
    }

    private int findHeightOfTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int height = -1;
        while (!queue.isEmpty()) {
            ++height;
            int n = queue.size();
            for (int i = 0; i < n; ++i) {
                TreeNode node = queue.poll();
                if (null != node) {
                    if (null != node.left) {
                        queue.add(node.left);
                    }
                    if (null != node.right) {
                        queue.add(node.right);
                    }
                }
            }
        }
        return height;
    }

    private void dfsFillMatrix(List<List<String>> matrix, TreeNode node, int height, int r, int c) {
        matrix.get(r).set(c, node.val + "");
        if (null != node.left) {
            dfsFillMatrix(matrix, node.left, height, r + 1, c - (int) Math.pow(2, height - r - 1));
        }
        if (null != node.right) {
            dfsFillMatrix(matrix, node.right, height, r + 1, c + (int) Math.pow(2, height - r - 1));
        }
    }
}
